package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.ArrayList;
import java.util.List;

public class _39_combination_sum {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] candidates;
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        dfs(0, target);
        return res;
    }
    
    void dfs(int index, int remaining) {
        if (index == candidates.length) return;
        if (remaining == 0) res.add(new ArrayList<>(path));
        else {
            dfs(index + 1, remaining);
            if (remaining - candidates[index] >= 0) {
                path.add(candidates[index]);
                dfs(index, remaining - candidates[index]);
                path.remove(path.size() - 1);
            }
        }
    }
    
}
